#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int negative = 0, n = nums.size(), minN = INT_MAX;
        for (int num : nums)
        {
            if (num < 0) ++negative;
            minN = min(minN, abs(num));
        }
        int ret = 0;
        if (negative > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; ++i)
                ret += -nums[i];
            for (int i = k; i < n; ++i)
                ret += nums[i];
        }
        else
        {
            for (int num : nums) ret += abs(num);
            if ((k - negative) & 1)
                ret -= 2 * minN;
        }
        return ret;
    }

    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<int> index(n);
        for (int i = 0; i < n; ++i)
            index[i] = i;
        sort(index.begin(), index.end(), [&](int i, int j)
            {
                return heights[i] > heights[j];
            });
        vector<string> ret;
        for (int i = 0; i < n; ++i)
        {
            ret.push_back(names[index[i]]);
        }
        return ret;
    }

    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> index(n);
        for (int i = 0; i < n; ++i)
            index[i] = i;
        sort(index.begin(), index.end(), [&](int i, int j)
            {
                return nums2[i] < nums2[j];
            });
        sort(nums1.begin(), nums1.end());
        vector<int> ret(n);
        int i = 0, j = 0, k = n - 1;
        while (j <= k)
        {
            if (nums1[i] > nums2[index[j]])
            {
                ret[index[j++]] = nums1[i];
            }
            else
            {
                ret[index[k--]] = nums1[i];
            }
            ++i;
        }
        return ret;
    }

    int longestPalindrome(string s) {
        unordered_map<char, int> hash;
        for (char c : s)
        {
            ++hash[c];
        }
        int ret = 0;
        for (auto& [k, v] : hash)
        {
            ret += v / 2 * 2;
        }
        return ret < s.size() ? ret + 1 : ret;
    }

    vector<int> diStringMatch(string s) {
        int n = s.size();;
        vector<int> nums(n + 1);
        for (int i = 0; i <= n; ++i)
        {
            nums[i] = i;
        }
        vector<int> ret;
        int left = 0, right = n;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == 'I')
            {
                ret.push_back(nums[left++]);
            }
            else
            {
                ret.push_back(nums[right--]);
            }
        }
        ret.push_back(nums[left]);
        return ret;
    }

    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end(), less<int>());
        sort(s.begin(), s.end(), less<int>());
        int i = 0, j = 0, ret = 0;
        while (i < s.size() && j < g.size())
        {
            if (s[i] >= g[j]) ++ret, ++j;
            ++i;
        }
        return ret;
    }

    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return to_string(nums[0]);
        if (n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
        string ans;
        ans += to_string(nums[0]) + "/" + "(";
        for (int i = 1; i < n - 1; ++i)
        {
            ans += to_string(nums[i]) + "/";
        }
        ans += to_string(nums[n - 1]) + ")";
        return ans;
    }

    int jump(vector<int>& nums) {
        int step = 0, maxPos = 0, end = 0;
        for (int i = 0; i < nums.size() - 1; ++i)
        {
            maxPos = max(maxPos, i + nums[i]);
            if (i == end)
            {
                end = maxPos;
                ++step;
            }
        }
        return step;
    }

    int jump(vector<int>& nums) {
        int step = 0, n = nums.size();
        int left = 0, right = 0, maxPos = 0;
        while (right < n)
        {
            if (maxPos >= n - 1) return step;
            for (int i = left; i <= right; ++i)
            {
                maxPos = max(maxPos, nums[i] + i);
            }
            ++step;
            left = right + 1;
            right = maxPos;
        }
        return step;
    }

    int jump(vector<int>& nums) {
        int n = nums.size(), INF = 0x3f3f3f3f;
        vector<int> dp(n, INF);
        dp[0] = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (j + nums[j] >= i) dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        return dp[n - 1];
    }

    bool canJump(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0, maxPos = 0;
        while (left <= right)
        {
            if (maxPos >= n - 1) return true;
            for (int i = left; i <= right; ++i)
            {
                maxPos = max(maxPos, i + nums[i]);
            }
            left = right + 1;
            right = maxPos;
        }
        return false;
    }

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = cost.size();
        vector<int> diff(n);
        for (int i = 0; i < n; ++i)
            diff[i] = gas[i] - cost[i];
        for (int i = 0; i < n; ++i)
        {
            int start = i;
            int m = 0, l = 0;
            while (m >= 0)
            {
                if (l == n) return start;
                m += diff[start++];
                if (start == n) start = 0;
                ++l;
            }
        }
        return -1;
    }

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = cost.size();
        vector<int> diff(n);
        for (int i = 0; i < n; ++i)
        {
            int m = 0;
            for (int step = 0; step < n; ++step)
            {
                int index = (i + step) % n;
                m += gas[index] - cost[index];
                if (m < 0)
                {
                    i = i + step;
                    break;
                }
            }
            if (m >= 0) return i;
        }
        return -1;
    }
};